/**
 * @file bfs.cpp
 * @author Wang Bo (1276106221@qq.com)
 * @brief 
 * Breadth-First Search 广度优先搜索
 * 为了演示，使用固定的图生成函数
 * @version 0.1
 * @date 2021-07-09
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#include "Graph.hpp"
#include <map>
#include <queue>
#include <set>

template <typename T>
auto createGraph() {
    Graph<T> G(9);
    std::map<uint32_t, vector<std::pair<size_t, T>>> edges;
    edges[1] = { {2, 2}, {5, 3} };
    edges[2] = { {1, 2}, {5, 5}, {4, 1} };
    edges[3] = { {4, 2}, {7, 3} };
    edges[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
    edges[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
    edges[6] = { {4, 4}, {7, 4}, {8, 1} };
    edges[7] = { {3, 3}, {6, 4} };
    edges[8] = { {4, 5}, {5, 3}, {6, 1} };
    for (auto& i : edges)
        for (auto& j : i.second)
            G.addEdge(Edge<T>{i.first, j.first, j.second});
    return G;
}

template <typename T>
auto breadthFirstSearch(const Graph<T>& G, size_t dest) {
    std::queue<size_t> queue;
    vector<size_t> visitOrder;
    std::set<size_t> visited;
    queue.push(1); //假定从1号顶点开始搜索
    while (!queue.empty()) {
        auto currentVertex = queue.front();
        queue.pop();
        //若顶点尚未被到访，则访问
        if (visited.find(currentVertex) == visited.end()) {
            //访问时将顶点加入visited集合
            visited.insert(currentVertex);
            //将访问顺序输出到visitOrder数组中
            visitOrder.push_back(currentVertex);
            //将该顶点所有边所连接的顶点压入队列
            for (const auto& e : G.edgesFromVertex(currentVertex))
                queue.push(e.dest);
        }
    }
    return visitOrder;
}

template <typename T>
void testBFS() {
    auto G = createGraph<T>();
    cout << G << endl;
    cout << "BFS Order of vertices:\n";
    auto BFSVisitOrder = breadthFirstSearch<T>(G, 1);
    for (const auto& v : BFSVisitOrder)
        cout << v << " -> ";
    cout << "finish\n";
}

int main(int argc, const char** argv) {
    using T = uint32_t;
    testBFS<T>();
    return 0;
}